package oj;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 郝文雪
 * @date 2022/8/25 15:50
 * @Description Test
 */
public class LC1382 {
    List<Integer> list=new ArrayList<>();
    public TreeNode balanceBST(TreeNode root) {
        inorder(root);
        return helper(0,list.size()-1);
    }
    private TreeNode helper(int left,int right){
        int mid=(left+right)/2;
        TreeNode root=new TreeNode(list.get(mid));
        if(left<=mid-1){
            root.left=helper(left,mid-1);
        }
        if(right>=mid+1){
            root.right=helper(mid+1,right);
        }
        return root;
    }
    private void inorder(TreeNode root){
        if(root.left!=null){
            inorder(root.left);
        }
        list.add(root.val);
        if(root.right!=null){
            inorder(root.right);
        }
    }
}
